package leetcode.day;


import java.math.BigInteger;
import java.util.Arrays;

// 1220. 统计元音字母序列的数目
public class CountVowelPermutation {

    public static void main(String[] args) {

        System.out.println(countVowelPermutation3(3));
    }

    static int MOD = (int) 1e9 + 7;

    public static int countVowelPermutation(int n) {
        long[][] f = new long[n][5];
        Arrays.fill(f[0], 1);
        for (int i = 0; i < n - 1; i++) {
            // 每个元音 'a' 后面都只能跟着 'e'
            f[i + 1][1] += f[i][0];
            // 每个元音 'e' 后面只能跟着 'a' 或者是 'i'
            f[i + 1][0] += f[i][1];
            f[i + 1][2] += f[i][1];
            // 每个元音 'i' 后面 不能 再跟着另一个 'i'
            f[i + 1][0] += f[i][2];
            f[i + 1][1] += f[i][2];
            f[i + 1][3] += f[i][2];
            f[i + 1][4] += f[i][2];
            // 每个元音 'o' 后面只能跟着 'i' 或者是 'u'
            f[i + 1][2] += f[i][3];
            f[i + 1][4] += f[i][3];
            // 每个元音 'u' 后面只能跟着 'a'
            f[i + 1][0] += f[i][4];
            for (int j = 0; j < 5; j++) {
                f[i + 1][j] %= MOD;
            }
        }
        long ans = 0;
        for (int i = 0; i < 5; i++) {
            ans += f[n - 1][i];
        }
        return (int) (ans % MOD);

    }

    // 方法一 ： 状态机、动态规划 二维DP
    public int countVowelPermutation2(int n) {
        if (n == 1) {
            return 5;
        }
        long[][] dp = new long[n + 1][5]; // 状态机DP数组：对应长度为 i 且五个元音字母结尾的字符串个数
        for (int i = 0; i < dp[0].length; i++) {
            dp[1][i] = 1;
        }
        long sum = 0L;
        long mod = (long) (Math.pow(10, 9) + 7);
        for (int i = 2; i < n + 1; i++) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % mod;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % mod;
            dp[i][3] = dp[i - 1][2] % mod;
            dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % mod;
        }
        for (int i = 0; i < 5; i++) {
            sum = (sum + dp[n][i]) % mod;
        }
        return (int) sum;
    }

    // dp---error 需要全部转换为大数据类型
    public static int countVowelPermutation3(int n) {
        BigInteger m = BigInteger.valueOf((int) (1e9 + 7));
        BigInteger[][] f = new BigInteger[n][5];
        Arrays.fill(f[0], BigInteger.valueOf(1));
        for (int i = 1; i < n; i++) {
            f[i][0] = (f[i - 1][1].add(f[i][2]).add(f[i][4])).mod(m);
            f[i][1] = (f[i - 1][2].add(f[i][0])).mod(m);
            f[i][2] = (f[i - 1][1].add(f[i][3])).mod(m);
            f[i][3] = f[i - 1][2].mod(m);
            f[i][4] = ((f[i][2]).add(f[i][3])).mod(m);
        }
        return (f[n - 1][0].add(f[n - 1][1]).add(f[n - 1][2]).add(f[n - 1][3])
                .add(f[n - 1][4]).mod(m)).intValue();
    }
}
